// 718. 最长重复子数组
// 给两个整数数组 nums1 和 nums2 ，
// 返回 两个数组中 公共的 、长度最长的子数组的长度 。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  const len1 = nums1.length
  const len2 = nums2.length

  // !!!!! 找子数组或者公共子数组，一般就这么定义 dp 含义
  // dp[i][j] 表示
  // 以 nums1[i] 和 nums2[j] 结尾
  // 的最长公共子数组最大长度
  const dp = new Array(len1 + 1).fill(0).map(
    () => new Array(len2 + 1).fill(0)
  )

  let ans = 0
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      // 如果这道题是找子序列，就要再从 dp[i - 1][j] 和 dp[i][j - 1] 递推了
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      }
      ans = Math.max(ans, dp[i][j])
    }
  }

  return ans
}

console.log(
  findLength(
    [0, 1, 1, 1, 1],
    [1, 0, 1, 0, 1]
  )
)
